The Open Shortest Path First (hereinafter “OSPF”) protocol is a hierarchical Interior Gateway Protocol (hereinafter “IGP”) for routing an internet protocol, using a link-state in the individual areas that make up the hierarchy. A computation based on Dijkstra's algorithm is used to calculate the shortest path tree inside each area.
A Link-State Database (hereinafter “LSDB”) is constructed as a tree-image of the network topology, and identical copies of the LSDB are updated periodically on all routers and each OSPF-aware area. The OSPF-aware area is a region of the network included in the OSPF area type. By convention, area 0 represents the core, or the backbone region, of the OSPF-enabled network; and other OSPF area numbers may be designated to serve other reasons of an enterprise network. However, every additional OSPF area must have a direct or virtual connection to the backbone OSPF area.
OSPF is perhaps the most widely used IGP in large enterprise networks. Another protocol, IS-IS, is more common in large service providers networks. The most widely used Exterior Gateway Protocol (hereinafter “EGP”) is Border Gateway Protocol (hereinafter “BGP”). The OSPF protocol can operate securely, optionally using a clear text password or using MD5 to authenticate peers before performing adjacencies, and before accepting Link-State Advertisements (hereinafter “LSA”). MD5 is message-digest algorithm 5. MD5 is a cryptography widely used in cryptographic hash function with a 128-bit hash value. MD5 is an internet standard RFC1321. MD5 has been employed in a wide variety of security applications and is also commonly used to check the integrity of files. An MD5 hash is typically expressed as a thirty-two (32) character hexadecimal number. A natural successor to the Routing Information Protocol, OSPF was classless—or able to use variable length subnet masking from its inception. Multicast extensions to OSPF, the multicast open shortest path first protocols, have been identified but these are not widely used at present.
Routers in the same broadcasting domain or at each end of a point-to-point telecommunications link formed adjacencies when they have detected each other. This detection occurs when a router “sees” itself in a hello packet (e.g., reads its own ID in the hello packet). This is called a two way state at its most basic relationship. The routers elect a designated router (hereinafter “DR”) and a backup designator router (hereinafter “BDR”) which act as a hub to reduce traffic between routers. OSPF uses both unicast and multicast to send “hello packets” and link-state updates. Multicast addresses 224.0.0.5 (all OSPF/link-state routers) and 224.0.0.6 (all designated routers) are reserved for OSPF. In contrast to the routing information protocol or the border gateway protocol, OSPF does not use TCP or UDP, but instead uses IP directly via IP protocol 89. OSPF handles its own error detection and correction. Therefore, OSPF does not need TCP or UDP functions.
An OSPF network is divided into areas, which have a 32-bit area identifiers commonly, but not always, written in the dotted decimal format of an IP address. Area identifiers are not IP addresses, and may duplicate, without conflict, any IP address.
OSPF uses path cost as its basic routing metric, which was defined by the standard not to equate to any standard values such as speed, so that the network designer could pick a metric important to the design. In practice, it is determined by the speed (e.g., bandwidth) of the interface addressing the given route, although that tends to do network specific scaling factors now that links faster than 100 MB per second are common.
However, metrics are only directly comparable when of the same type. There are four types of metrics, with the most preferred types listed in order below. An intra-area route is always preferred to an inter-area route regardless of the metric and so on for the other types.                1. Intra-area;        2. Inter-area;        3. External type 1, which includes both the external path cost and a sum of internal path costs to the autonomous system border routers (hereinafter “ASBR”) that advertises the route; and        4. External type 2, the value which is solely that of the external path cost.        
OSPF traffic engineering is an extension of OSPF, extending the idea of route preference to include traffic engineering as defined by RFC3630. Traffic engineering extensions to OSPF add dynamic properties to the route calculation algorithm. These properties include maximum reservable bandwidth, unreservable bandwidth, and available bandwidth. OSPF traffic engineering is commonly used within Multiprotocol Label Switching (hereinafter “MPLS”) and generalized multiprotocol label switching networks, as a means to determine the topology over which MPLS paths can be established. MPLS then uses its own path setup and forwarding protocols, once it has the full IP routing map. OSPF has the following router types:                1. Area border router (hereinafter “ABR”);        2. Autonomous system border router (hereinafter “ASBR”);        3. Internal router (hereinafter “IR”); and        4. Backbone router (hereinafter “BR”).        
The routers are classified by a router type. The router types are attributes of an OSPF process. A given physical router may have one or more OSPF processes. For example, a router that is connected to more than one area, and which receives routes from a BGP process connected to another autonomous system is both an ABR and an ASBR.
An ABR is a router that connects one or more OSPF areas to the main backbone network. The ABR is considered a member of all areas to which it is connected. The ABR keeps multiple copies of the link-state database in memory, one for each area to which the router is connected. The ASBR is a router that is connected to one or more autonomous systems and that exchanges routing information with routers and other autonomous systems. ASBRs typically also run a non-IGP routing protocol (e.g., BGP), or use static routes, or both. The ASBR is used to distribute routes received from other autonomous systems throughout its own autonomous system. The IR router is a router that has only OSPF neighbor relationships with routers in the same area. The backbone router is a router that is part of the OSPF backbone. By definition, this includes all area border routers since those routers pass routing information between areas. However, a backbone router may also be a router that connects only to other backbone routers, and is therefore not part of any other area.
A designated router (hereinafter “DR”) is a router interface selected among all routers on a particular multicast network segment, generally assumed to be broadcast multiaccess (i.e., data is made available simultaneously to multiple users or computers). Special techniques, often vendor dependent, may be needed to support the DR function on non broadcast multicasts (hereinafter “NBMA”) media. The individual circuits of an NBMA subnet are usually configured as point-to-point lines.
A given physical router can have some interfaces that are designated, others that are backup designated (e.g., a BDR), and others that are non-designated. If no router is a DR or BDR on a given subnet, the BDR is first elected, and then the second election is held if there is more than one BDR. The router winning the second election becomes a DR, or if there is no other BDR, designates itself DR. The DR is elected on the following default criteria:                If the priority setting on an OSPF router is set to 0 that means it can never become a DR or BDR.        When a DR fails and the BDR takes over, there is another election to see who becomes the replacement BDR.        The router sending the hello packets with the highest priority wins the election.        If two or more routers tie with the highest priority setting, the router with the highest router ID wins. A RID is a highest logical IP address configured on the router, if no logical, i.e., loop back IP address, is set and the router uses the highest IP address configured on its active interfaces.        Usually the router with the second highest priority number becomes the BDR        The priority value ranges between 0 and 254, but the higher value increases its chances of becoming the BR or BDR.        If a higher priority OSPF router comes online after the election has taken place, it will not become the DR or BDR until after the DR or BDR fail.        
If the current DR goes down the current BDR becomes the new DR and a new election takes place to find another BDR. The new DR then goes down and the original DR is now available, it becomes the DR again, but no change is made to the current BDR.
DRs reduce network traffic by providing a source for routing updates, the DR maintains a complete topology table of the network and sends the updates to other routers via multicast. This way all routers do not have to constantly update each other, and can rather get all their updates from a single source. The use of multicasting further reduces the network load. DRs and BDRs are always set up elected on broadcast networks (e.g., Ethernet LANs.). DRs can also be elected on NBMA (non broadcast multi access) networks such as frame, relay or ATM. DRs or BDRs are not elected on point-to-point links (such as a point-to-point LAN connection) because the two routers on either side of the link must become fully adjacent and the bandwidth between them cannot be further optimized.
A backup designator router BDR is a router that becomes a designated router if the current designated router has a problem or fails. The BDR is the OSPF router with the second highest priority at the time of the last election. Each router has a router identifier, customarily written in the dotted decimal format (e.g., 1.2.3.4) of an IP address. The way in which the router ID is determined is implementation specific. However, the router ID does not have to be a valid IP address, or any IP address, present in the routing domain, although it frequently will be advertised within the domain for trouble shooting purposes.
OSPF can be used on a wide area network (hereinafter “LAN” or “LANs”). LAN is a computer network that covers a broad area (i.e., any network whose communication links cross metropolitan, regional, or national boundaries). The LAN is a long haul connection that is a network that uses routers and public communication links. The internet is one form of LAN and is most notably, the largest.
LANs are used to connect local area networks (hereinafter “LANs” or “LAN”) and other types of networks together, so that users and computers in one location communicate with users and computers in another location. Many LANs are built for one particular organization and are private. Others, built by internet service providers (hereinafter “ISPs”), provide connections from an organizations LAN to the internet. LANs are often built using leased lines at each end of the leased line, a router connect the LAN on one side and a hub within the LAN on the other. Leased lines can be very expensive. Instead of using leased lines, LANs can also be built using less costly circuit, switching, or packet switching methods. Network protocols including TCIP deliver transport and addressing functions. Protocols including packet over SONNET/SDH, MPLS, ATM and Frame rarely are used often by service providers to deliver the links that are used in the LAN.
Currently, using OSPF a DR router can not communicate through the LAN to other routers connected to the LAN. All routers send OSPF hello packets once every one second. This hello packet contains within the packet a list of the routers that the originating router can access in a network. If a router fails, then the routers in the network would discover that failure after four seconds. The other routers in the network would then cease to include the failed routers ID within their hello packets. The current OSPF standard specifies this process as establishing a minimum safe duration for “declaring a router” dead. Therefore, the minimum time for discovering a router failure and then rerouting around the failure can take at least four seconds. In some cases, faster timers (Hello timers) are used. For example, a Hello time of zero (0) can be used in certain proprietary systems. However, such systems require that all connected routers utilize the same Request For Comments standard. Typically, the router dead time would be 4 times whatever value is chosen as the Hello interval. However, using this minor departure from the Request For Comments (hereinafter “RFC”) standard increases the load on the router. As a result, scalability of the system is limited. What is needed is a method and system to detect and switch around a failed router in less than four seconds in OSPF networks of various sizes.